home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.06 / ChallengeHexGame.sit / Challenge, Hex Game / Hex Strategy.c < prev    next >
Text File  |  1997-05-07  |  39KB  |  1,367 lines
  1. // *********************************************************
  2. // Programmer: Gregory Cooper
  3. // Date: Februrary 22, 1997
  4. // Function: a strategy for the game of Hex
  5. // Written for: March, 1997 MacTech Programmer's Challenge
  6. //
  7. // General idea: My strategy tries to find the quickest
  8. // routes across the board, both for itself and for its
  9. // opponent.  If the opponent has a better, shorter route
  10. // than my strategy does, then my strategy makes a defensive
  11. // move (one that makes it more difficult for the opponent
  12. // to complete his route).  Otherwise, it makes an offensive
  13. // move (one which brings its own route closer to
  14. // completion).  It re-traces the routes during each turn,
  15. // looking for necessary modifications and scoring changes.
  16. // *********************************************************
  17.  
  18. #include "Storage.h"
  19.  
  20. // an enumeration for move types
  21. typedef enum
  22. {
  23.     // counter-clockwise from right
  24.     right,                // 0
  25.     upRightTwoBridge,    // 30
  26.     upRight,            // 60
  27.     upTwoBridge,        // 90
  28.     upLeft,                // 120
  29.     upLeftTwoBridge,    // 150
  30.     left,                // 180
  31.     downLeftTwoBridge,    // 210
  32.     downLeft,            // 240
  33.     downTwoBridge,        // 270
  34.     downRight,            // 300
  35.     downRightTwoBridge,    // 330
  36.     noDirection            // undefined
  37. } Direction;
  38.  
  39. // a data structure for representing potential routes to
  40. // edges or to other chips
  41. typedef struct Path
  42. {
  43.     long        row;            // row of piece on board
  44.     long        col;            // column of piece on board
  45.     Direction    nextDirection;    // direction to next piece
  46.     Direction    prevDirection;    // direction to prev piece
  47.     Boolean        occupied;        // location actually taken?
  48.     Boolean        center;            // origin of path?
  49.     struct Path    *next;            // next piece in path
  50.     struct Path    *prev;            // previous piece in path
  51. } Path;
  52.  
  53. // a data type for the playing chips
  54. typedef enum
  55. {
  56.     empty,
  57.     blue,    // plays first
  58.     red        // plays second
  59. } Chip;
  60.  
  61. // an enumeration for disposing of unneeded paths
  62. // (used by the BetterPath function and its clients)
  63. typedef enum
  64. {
  65.     leaveBad,    // indicates that inferior strategy should
  66.                 // be left alone
  67.     forgetBad    // indicates that inferior strategy should
  68.                 // be disposed
  69. } PathAction;
  70.  
  71. // an enumeration for the edges
  72. typedef enum
  73. {
  74.     leftEdge,
  75.     rightEdge,
  76.     topEdge,
  77.     bottomEdge
  78. } Edge;
  79.  
  80. // an enumeration for path disruptions
  81. typedef enum
  82. {
  83.     noDisruption,    // move did not block path
  84.     inTwoBridge,    // move occupied part of a two-bridge
  85.     inSpot            // move occupied a strategic location
  86. } Disruption;
  87.  
  88. Path *BestPathAcrossBoard(long boardSize, Chip *theBoard,
  89.     long startRow, long startCol, Chip color);
  90. // tries to find a path across the board through
  91. // (startRow, startCol)
  92. // PRECONDITIONS: boardSize is the number of rows or columns
  93. // on the board; theBoard stores information about the
  94. // board; (startRow, startCol) indicates a piece of the
  95. // given color on the board; color indicates which player
  96. // for whom the path is to be found
  97. // POSTCONDITIONS: returns a pointer to the path found,
  98. // beginning with (startRow, startCol), or returns nil
  99. // if no path exists
  100.  
  101. Boolean ExtendPathToEdge(long boardSize, Chip *theBoard,
  102.     Path *path, Edge edge);
  103. // tries to find a path from path to the given edge
  104. // PRECONDITIONS: path is an incomplete path, edge is one
  105. // of the four edges, boardSize is the number of rows or
  106. // columns on the board, theBoard defines the playing board
  107. // POSTCONDITIONS: if a path from the edge exists, it is
  108. // found and the value true is returned; otherwise, all
  109. // memory associated with the path is freed and it returns
  110. // false
  111.  
  112. void PrioritizeMoves(Edge edge, Direction moveList[12]);
  113. // determines the order in which potential moves in a path
  114. // should be attempted
  115. // PRECONDITIONS: edge is the edge to which we are trying
  116. // to move
  117. // POSTCONDITIONS: moveList contains the moves in order
  118. // from most to least direct
  119.  
  120. Boolean PossibleMove(long boardSize, Chip *theBoard,
  121.     long row, long col, Path *path, Direction move,
  122.     Chip color);
  123. // determines whether placing a piece in a given location
  124. // is feasible
  125. // PRECONDITIONS: boardSize is the number of rows or columns
  126. // on the board; theBoard defines the board; (row, col)
  127. // is the piece from which we are moving; move is the
  128. // direction in which we are moving; color is the color of
  129. // the player
  130. // POSTCONDITIONS: returns true if the given move is
  131. // possible, false otherwise
  132.  
  133. void FindNewLocation(long row, long col, Direction move,
  134.     long *newRow, long *newCol);
  135. // determines the location of a piece adjacent to another
  136. // piece in a given direction
  137. // PRECONDITIONS: (row, col) indicates the initial piece,
  138. // move is the direction of the move
  139. // POSTCONDITIONS: (*newRow, *newCol) contain the location
  140. // of the new piece
  141.  
  142. Direction OppositeDirection(Direction move);
  143. // determines the direction opposite a given direction
  144. // PRECONDITIONS: move is a direction
  145. // POSTCONDITIONS: returns the direction opposite move
  146.  
  147. Boolean OnBoard(long boardSize, long row, long col);
  148. // determines whether a given piece lies on the board
  149. // PRECONDITIONS: boardSize is the size of the board,
  150. // (row, col) is the location of the desired piece
  151. // POSTCONDITIONS: returns whether the piece is
  152. // within the boundaries of the board
  153.  
  154. Boolean IsTwoBridge(Direction move);
  155. // determines whether a connection in a given direction is
  156. // a two-bridge
  157. // PRECONDITIONS: move is the direction of the desired
  158. // connection
  159. // POSTCONDITIONS: returns true if the connection is a 
  160. // two-bridge; otherwise returns false
  161.  
  162. Boolean TwoBridgeFree(long boardSize, Chip *theBoard,
  163.     long row, long col, Direction move);
  164. // determines whether a given two-bridge is free
  165. // PRECONDITIONS: (row, col) contains one of the pieces in
  166. // in the two-bridge, move is the direction of the bridge,
  167. // boardSize and theBoard define the board
  168. // POSTCONDITIONS: returns true if the spaces in between
  169. // are free; otherwise, returns false
  170.  
  171. Boolean PieceOnEdge(long row, long col, long boardSize,
  172.     Edge edge);
  173. // determines whether a given piece is on a desired edge
  174. // PRECONDITIONS: (row, col) indicate a piece, boardSize is
  175. // the number of rows or columns on the board, edge is the
  176. // desired edge
  177. // POSTCONDITIONS: returns true if the piece is on the edge;
  178. // otherwise returns false
  179.  
  180. void FreePath(Path *path);
  181. // disposes the memory associated with a path
  182. // PRECONDITIONS: path points to a path
  183. // POSTCONDITIONS: the memory associated with the path is
  184. // freed.
  185.  
  186. Boolean ValidMove(long boardSize, Chip *theBoard,
  187.     long row, long col);
  188. // determines whether a desired move is legal
  189. // PRECONDITIONS: boardSize contains the number of rows or
  190. // columns on the board; theBoard defines the playing
  191. // board; (row, col) is the location of the intended move
  192. // POSTCONDITIONS: returns true if the piece is on the
  193. // board and not already taken; otherwise false
  194.  
  195. Disruption MoveInPath(Path *path, long row, long col);
  196. // determines whether a desired move is in a path
  197. // PRECONDITIONS: path describes a path across the board;
  198. // (row, col) defines the intended move
  199. // POSTCONDITIONS: returns noDisruption if the move is
  200. // not in the path, inTwoBridge if it threatens an
  201. // established two-bridge, or inSpot if it occupies a
  202. // location in the path (including a two-bridge whose
  203. // end-points have not been secured)
  204.  
  205. Boolean TwoBridgeThreatened(long row, long col,
  206.     long threatRow, long threatCol, Direction move);
  207. // determines whether a two-bridge is threatened by a given
  208. // move
  209. // PRECONDITIONS: (row, col) is the origin of a two-bridge;
  210. // (threatRow, threatCol) is the new move; move is the
  211. // direction of the two-bridge
  212. // POSTCONDITIONS: returns true if the two-bridge is
  213. // threatened by the move
  214.  
  215. void UpdatePath(Path *path, long row, long col);
  216. // updates a path when a move is made
  217. // PRECONDITIONS: path points to a path across the board;
  218. // (row, col) is the location of the move
  219. // POSTCONDITIONS: the location in the path is marked
  220. // as being occupied; sometimes, as when a two-bridge
  221. // is filled in (and destroyed), an extra node is added to
  222. // the path list
  223.  
  224. Direction GetDirection(long row1, long col1, long row2,
  225.     long col2);
  226. // determines the direction from one piece to another
  227. // PRECONDITIONS: (row1, col1) and (row2, col2) define
  228. // two pieces
  229. // POSTCONDITIONS: the direction from (row1, col1) to
  230. // (row2, col2) is returned
  231.  
  232. Path *BetterPath(Path *path1, Path *path2,
  233.     PathAction action);
  234. // determines which of two paths is superior to the other
  235. // PRECONDITIONS: path1 and path2 point to paths
  236. // POSTCONDITIONS: the better of the two paths is returned;
  237. // if action is forgetBad, then the inferior path is
  238. // disposed
  239.  
  240. long PathRating(Path *path);
  241. // rates a path
  242. // PRECONDITIONS: path is a path
  243. // POSTCONDITIONS: a rating for the path is returned
  244. // (always positive, low numbers are better)
  245.  
  246. void FillThreatenedTwoBridge(Path *path, long threatRow,
  247.     long threatCol, long *row, long *col);
  248. // determines where to move in order to secure a threatened
  249. // two-bridge
  250. // PRECONDITIONS: path points to a path;
  251. // (threatRow, threatCol) is the move which threatened the
  252. // two-bridge
  253. // POSTCONDITIONS: (row, col) is the move needed to secure
  254. // the free half of the two-bridge
  255.  
  256. Path *TakeDetour(long boardSize, Chip *theBoard, Path *path,
  257.     long row, long col, Chip color);
  258. // finds a new path after it has been disrupted
  259. // PRECONDITIONS: path points to a path; (row, col)
  260. // indicates a move which disrupted the path
  261. // POSTCONDITIONS: the path is corrected, if possible, so
  262. // that it avoids the opponent's piece, and it is then
  263. // returned; nil is returned if no new path can be found
  264.  
  265. void FindBestMove(Path *ourPath, Path *oppPath, long *row,
  266.     long *col);
  267. // TRIES to determine the best move
  268. // PRECONDITIONS: ourPath and oppPath are the expected
  269. // paths of the player and the opponent, respectively
  270. // POSTCONDITIONS: (*row, *col) indicate the chosen move,
  271. // which should be decent; if the opponent's path is better,
  272. // it should be a defensive move; if not, it should be
  273. // an offensive move; whenever possible, offensive and
  274. // defensive moves are made to coincide with one another
  275.  
  276. Boolean NextToEdge(long row, long col, long boardSize,
  277.     Edge edge);
  278. // determines if a piece is next to a given edge
  279. // PRECONDITIONS: (row, col) is a piece; boardSize is the
  280. // size of the board, edge is the edge we want to be near
  281. // POSTCONDITIONS: returns true if the piece if one hex
  282. // from the edge
  283.  
  284. Boolean Hex(long boardSize, long oppRow, long oppCol,
  285.     long *moveRow, long *moveCol, void *privStorage,
  286.     Boolean newGame, Boolean playFirst);
  287.  
  288. Boolean Hex(long boardSize, long oppRow, long oppCol,
  289.     long *moveRow, long *moveCol, void *privStorage,
  290.     Boolean newGame, Boolean playFirst)
  291. {
  292.     // board storage (preserved between turns)
  293.     static Chip    *theBoard;
  294.     // expected paths (also preserved between turns)
  295.     static Path *ourPath, *oppPath;
  296.     // a temporary path used for comparisons
  297.     Path *newPath;
  298.     Disruption disruption; // holds path disruptions
  299.     
  300.     if (newGame)
  301.     {
  302.         long i;
  303.         
  304.         // initialize the private storage allocation system
  305.         InitializeHeap(privStorage, 0x100000); // 1 MB
  306.         // initialize storage space for the board
  307.         theBoard = AllocateBlock(boardSize * boardSize);
  308.         for (i = 0; i < boardSize * boardSize; i++)
  309.             theBoard[i] = empty;
  310.         // indicate that no paths have yet been determined
  311.         ourPath = oppPath = nil;
  312.         if (playFirst)
  313.         {
  314.             // go in the middle
  315.             *moveRow = (boardSize - 1) / 2;
  316.             *moveCol = boardSize / 2;
  317.             // mark the chip on the board
  318.             theBoard[*moveRow * boardSize + *moveCol] =
  319.                 blue; // blue because we are moving first
  320.             // try to determine the shortest route across
  321.             // the board through the spot where we just
  322.             // moved
  323.             ourPath = BestPathAcrossBoard(boardSize,
  324.                 theBoard, *moveRow, *moveCol, blue);
  325.             return true;
  326.         } // end if
  327.     } // end if
  328.     // check the opponent's move
  329.     if (!ValidMove(boardSize, theBoard, oppRow, oppCol))
  330.         // if it is illegal, abort here
  331.         return false;
  332.     // mark the opponent's move on the board
  333.     theBoard[oppRow * boardSize + oppCol] =
  334.         playFirst ? red : blue;
  335.     // if the opponent's move was in his path (offensive)
  336.     if (MoveInPath(oppPath, oppRow, oppCol))
  337.         // update his path
  338.         UpdatePath(oppPath, oppRow, oppCol);
  339.     else // opponent did not continue his expected path
  340.     {
  341.         // try to find a probable route for the
  342.         // opponent through the piece where he just
  343.         // moved
  344.         newPath = BestPathAcrossBoard(boardSize, theBoard,
  345.             oppRow, oppCol, playFirst ? red : blue);
  346.         // if his new route is better than his old one, use
  347.         // it instead
  348.         oppPath = BetterPath(oppPath, newPath, forgetBad);
  349.     } // end else
  350.     // determine whether his move blocked or
  351.     // otherwise disrupted our path
  352.     disruption = MoveInPath(ourPath, oppRow, oppCol);
  353.     if (disruption == inTwoBridge)
  354.     {
  355.         // move into the other half of the
  356.         // two-bridge automatically
  357.         FillThreatenedTwoBridge(ourPath, oppRow, oppCol,
  358.             moveRow, moveCol);
  359.         // mark the move on the board
  360.         theBoard[*moveRow * boardSize + *moveCol] =
  361.             playFirst ? blue : red;
  362.         // update the path
  363.         UpdatePath(ourPath, *moveRow, *moveCol);
  364.     } // end if
  365.     else // no automatic response
  366.     {
  367.         if (disruption == inSpot)
  368.             // try to find a new path from just
  369.             // before the disruption (the unaffected
  370.             // part of the path can remain)
  371.             ourPath = TakeDetour(boardSize, theBoard,
  372.                 ourPath, oppRow, oppCol, playFirst ? blue :
  373.                 red);
  374.         // try to determine the best move and then make it
  375.         FindBestMove(ourPath, oppPath, moveRow, moveCol);
  376.         // if the move was invalid (happens when neither
  377.         // player has a path), just try to find a
  378.         // valid move
  379.         if (!ValidMove(boardSize, theBoard, *moveRow,
  380.             *moveCol))
  381.         {
  382.             Boolean moveFound = false;
  383.             for (*moveRow = 0; !moveFound && *moveRow
  384.                 < boardSize; (*moveRow)++)
  385.             {
  386.                 for (*moveCol = 0; !moveFound && *moveCol
  387.                     < boardSize; (*moveCol)++)
  388.                 {
  389.                     if (ValidMove(boardSize, theBoard,
  390.                         *moveRow, *moveCol))
  391.                     {
  392.                         moveFound = true;
  393.                         (*moveRow)--;
  394.                         (*moveCol)--;
  395.                     } // end if
  396.                 } // end for
  397.             } // end for
  398.         } // end if
  399.         // mark the move on the board
  400.         theBoard[*moveRow * boardSize + *moveCol] =
  401.             playFirst ? blue : red;
  402.         // check to see if the move was in our path
  403.         if (MoveInPath(ourPath, *moveRow, *moveCol))
  404.             // if so, update it
  405.             UpdatePath(ourPath, *moveRow, *moveCol);
  406.         else
  407.         {
  408.             // otherwise, try to find a path through the
  409.             // new location
  410.             newPath = BestPathAcrossBoard(boardSize,
  411.                 theBoard, *moveRow, *moveCol,
  412.                 playFirst ? blue : red);
  413.             
  414.             // if the new path is better than the
  415.             // old one, use it instead
  416.             ourPath = BetterPath(ourPath, newPath,
  417.                 forgetBad);
  418.         } // end else
  419.     } // end if
  420.     // if our move blocked the opponent's path,
  421.     // try to find him a new path from just before
  422.     // the disruption
  423.     if (MoveInPath(oppPath, *moveRow, *moveCol))
  424.         oppPath = TakeDetour(boardSize, theBoard, oppPath,
  425.         *moveRow, *moveCol, playFirst ? red : blue);
  426.     return true;
  427. } // end Hex
  428.  
  429. Path *BestPathAcrossBoard(long boardSize, Chip *theBoard,
  430.     long startRow, long startCol, Chip color)
  431. {
  432.     // initial path is just the starting hex
  433.     Path *thePath = AllocateBlock(sizeof (Path));
  434.     
  435.     thePath->row = startRow;
  436.     thePath->col = startCol;
  437.     thePath->occupied =     // should be true always
  438.         theBoard[startRow * boardSize + startCol] == color;
  439.     // no connections yet
  440.     thePath->prev = thePath->next = nil;
  441.     thePath->prevDirection = thePath->nextDirection =
  442.         noDirection;
  443.     thePath->center = true;
  444.     // find the best path from (startRow, startCol) to the
  445.     // top (if blue) or left (if red) edge
  446.     if (!ExtendPathToEdge(boardSize, theBoard, thePath,
  447.         color == blue ? topEdge : leftEdge))
  448.     {
  449.         FreePath(thePath);
  450.         return nil;
  451.     } // end if
  452.     // find the best path from (startRow, startCol) to the
  453.     // other friendly edge
  454.     if (!ExtendPathToEdge(boardSize, theBoard, thePath,
  455.         color == blue ? bottomEdge : rightEdge))
  456.     {
  457.         FreePath(thePath);
  458.         return nil;
  459.     } // end if
  460.     // if we made it here, we succeeded
  461.     return thePath;
  462. } // end BestPathAcrossBoard
  463.  
  464. Boolean ExtendPathToEdge(long boardSize, Chip *theBoard,
  465.     Path *path, Edge edge)
  466. {
  467.     Direction moveList[12]; // stores the move priorities
  468.     // which color we are
  469.     Chip color = edge == leftEdge || edge == rightEdge ?
  470.         red : blue;
  471.     long moveNum; // an index for when we try to move
  472.     // which way the path is going
  473.     Boolean goingForward = edge == rightEdge ||
  474.         edge == bottomEdge;
  475.     Boolean result; // did we succeed yet
  476.     
  477.     // prioritize the moves according to which edge we
  478.     // are seeking and the current location in the path
  479.     PrioritizeMoves(edge, moveList);
  480.     // stop if we are already at an edge
  481.     if (PieceOnEdge(path->row, path->col, boardSize, edge))
  482.         return true;
  483.     // see if we are next to the edge
  484.     if (NextToEdge(path->row, path->col, boardSize, edge))
  485.     {
  486.         Direction d;
  487.         long newRow, newCol;
  488.         
  489.         // make the simplest move to reach the edge
  490.         for (d = right; d < noDirection; d++)
  491.             if (!IsTwoBridge(d))
  492.             {
  493.                 FindNewLocation(path->row, path->col, d,
  494.                     &newRow, &newCol);
  495.                 if (PieceOnEdge(newRow, newCol, boardSize,
  496.                     edge) && ValidMove(boardSize, theBoard,
  497.                     newRow, newCol))
  498.                 {
  499.                     // allocate space for the new node
  500.                     Path *newNode =
  501.                         AllocateBlock(sizeof (Path));
  502.                     newNode->row = newRow;
  503.                     newNode->col = newCol;
  504.                     // determine if it has been secured or
  505.                     // not
  506.                     newNode->occupied = theBoard[
  507.                         newNode->row * boardSize +
  508.                         newNode->col] == color;
  509.                     // it is not the center (it is an
  510.                     // extension)
  511.                     newNode->center = false;
  512.                     // link the new node to the old path
  513.                     if (goingForward)
  514.                     {
  515.                         path->nextDirection = d;
  516.                         path->next = newNode;
  517.                         newNode->prevDirection =
  518.                             OppositeDirection(d);
  519.                         newNode->prev = path;
  520.                         newNode->next = nil;
  521.                         newNode->nextDirection =
  522.                             noDirection;
  523.                     } // end if
  524.                     else
  525.                     {
  526.                         path->prevDirection = d;
  527.                         path->prev = newNode;
  528.                         newNode->nextDirection =
  529.                             OppositeDirection(d);
  530.                         newNode->next = path;
  531.                         newNode->prev = nil;
  532.                         newNode->prevDirection =
  533.                             noDirection;
  534.                     } // end else
  535.                     return true;
  536.                 } // end if
  537.             } // end for
  538.     } // end if
  539.     // first look to connect with a piece that is already
  540.     // on the board
  541.     for (result = false, moveNum = 0;
  542.         !result && moveNum < 9; moveNum++)
  543.     {
  544.         // once a single move works, try to extend from
  545.         // the new location to the same edge
  546.         if (PossibleMove(boardSize, theBoard, path->row,
  547.             path->col, path, moveList[moveNum], color))
  548.         {
  549.             // allocate space for the new node
  550.             Path *newNode = AllocateBlock(sizeof (Path));
  551.             
  552.             // abort if there is not enough memory
  553.             if (!newNode)
  554.                 return false;
  555.             // define its position
  556.             FindNewLocation(path->row, path->col,
  557.                 moveList[moveNum], &newNode->row,
  558.                 &newNode->col);
  559.             // determine if it has been secured or not
  560.             newNode->occupied = theBoard[newNode->row *
  561.                 boardSize + newNode->col] == color;
  562.             // only make the move if there is already a
  563.             // connection
  564.             if (!newNode->occupied)
  565.             {
  566.                 FreeBlock(newNode);
  567.                 continue;
  568.             }
  569.             // it is not the center (it is an extension)
  570.             newNode->center = false;
  571.             // link the new node to the old path
  572.             if (goingForward)
  573.             {
  574.                 path->nextDirection = moveList[moveNum];
  575.                 path->next = newNode;
  576.                 newNode->prevDirection =
  577.                     OppositeDirection(moveList[moveNum]);
  578.                 newNode->prev = path;
  579.                 newNode->next = nil;
  580.                 newNode->nextDirection = noDirection;
  581.             } // end if
  582.             else
  583.             {
  584.                 path->prevDirection = moveList[moveNum];
  585.                 path->prev = newNode;
  586.                 newNode->nextDirection =
  587.                     OppositeDirection(moveList[moveNum]);
  588.                 newNode->next = path;
  589.                 newNode->prev = nil;
  590.                 newNode->prevDirection = noDirection;
  591.             } // end else
  592.             // see if we can get to an edge
  593.             if (ExtendPathToEdge(boardSize, theBoard,
  594.                 newNode, edge))
  595.             {
  596.                 result = true;
  597.             } // end if
  598.             else
  599.             {
  600.                 // undo the added node
  601.                 FreeBlock(newNode);
  602.                 if (goingForward)
  603.                 {
  604.                     path->next = nil;
  605.                     path->nextDirection = noDirection;
  606.                 } // end if
  607.                 else
  608.                 {
  609.                     path->prev = nil;
  610.                     path->prevDirection = noDirection;
  611.                 } // end else
  612.             } // end else
  613.         } // end if
  614.     } // end for
  615.     // try moves until we run out or one works
  616.     for (moveNum = 0; !result && moveNum < 7; moveNum++)
  617.     {
  618.         // once a single move works, try to extend from
  619.         // the new location to the same edge
  620.         if (PossibleMove(boardSize, theBoard, path->row,
  621.             path->col, path, moveList[moveNum], color))
  622.         {
  623.             // allocate space for the new node
  624.             Path *newNode = AllocateBlock(sizeof (Path));
  625.             
  626.             // abort if there is not enough memory
  627.             if (!newNode)
  628.                 return false;
  629.             // define its position
  630.             FindNewLocation(path->row, path->col,
  631.                 moveList[moveNum], &newNode->row,
  632.                 &newNode->col);
  633.             // determine if it has been secured or not
  634.             newNode->occupied = theBoard[newNode->row *
  635.                 boardSize + newNode->col] == color;
  636.             // it is not the center (it is an extension)
  637.             newNode->center = false;
  638.             // link the new node to the old path
  639.             if (goingForward)
  640.             {
  641.                 path->nextDirection = moveList[moveNum];
  642.                 path->next = newNode;
  643.                 newNode->prevDirection =
  644.                     OppositeDirection(moveList[moveNum]);
  645.                 newNode->prev = path;
  646.                 newNode->next = nil;
  647.                 newNode->nextDirection = noDirection;
  648.             } // end if
  649.             else
  650.             {
  651.                 path->prevDirection = moveList[moveNum];
  652.                 path->prev = newNode;
  653.                 newNode->nextDirection =
  654.                     OppositeDirection(moveList[moveNum]);
  655.                 newNode->next = path;
  656.                 newNode->prev = nil;
  657.                 newNode->prevDirection = noDirection;
  658.             } // end else
  659.             // see if we are at the edge or can get to one
  660.             if (ExtendPathToEdge(boardSize, theBoard,
  661.                 newNode, edge))
  662.             {
  663.                 result = true;
  664.             } // end if
  665.             else
  666.             {
  667.                 // undo the added node
  668.                 FreeBlock(newNode);
  669.                 if (goingForward)
  670.                 {
  671.                     path->next = nil;
  672.                     path->nextDirection = noDirection;
  673.                 } // end if
  674.                 else
  675.                 {
  676.                     path->prev = nil;
  677.                     path->prevDirection = noDirection;
  678.                 } // end else
  679.             } // end else
  680.         } // end if
  681.     } // end for
  682.     
  683.     // return true if we succeeded, false if not
  684.     return result;
  685. } // end ExtendPathToEdge
  686.  
  687. void PrioritizeMoves(Edge edge, Direction move[12])
  688. {
  689.     switch (edge)
  690.     {
  691.         case leftEdge:
  692.             // in order from most to least direct
  693.             move[0] = downLeftTwoBridge;
  694.             move[1] = upLeftTwoBridge;
  695.             move[2] = downTwoBridge;
  696.             move[3] = left;
  697.             move[4] = downLeft;
  698.             move[5] = upLeft;
  699.             move[6] = downRight;
  700.             move[7] = upRight;
  701.             move[8] = right;
  702.             move[9] = upTwoBridge;
  703.             move[10] = downRightTwoBridge;
  704.             move[11] = upRightTwoBridge;
  705.             break;
  706.         case rightEdge:
  707.             // in order from most to least direct
  708.             move[0] = upRightTwoBridge;
  709.             move[1] = downRightTwoBridge;
  710.             move[2] = upTwoBridge;
  711.             move[3] = right;
  712.             move[4] = upRight;
  713.             move[5] = downRight;
  714.             move[6] = upLeft;
  715.             move[7] = downLeft;
  716.             move[8] = left;
  717.             move[9] = downTwoBridge;
  718.             move[10] = upLeftTwoBridge;
  719.             move[11] = downLeftTwoBridge;
  720.             break;
  721.         case topEdge:
  722.             // in order from most to least direct
  723.             move[0] = upTwoBridge;
  724.             move[1] = upLeftTwoBridge;
  725.             move[2] = upRightTwoBridge;
  726.             move[3] = upLeft;
  727.             move[4] = upRight;
  728.             move[5] = left;
  729.             move[6] = right;
  730.             move[7] = downLeft;
  731.             move[8] = downRight;
  732.             move[9] = downLeftTwoBridge;
  733.             move[10] = downRightTwoBridge;
  734.             move[11] = downTwoBridge;
  735.             break;
  736.         case bottomEdge:
  737.             // in order from most to least direct
  738.             move[0] = downTwoBridge;
  739.             move[1] = downRightTwoBridge;
  740.             move[2] = downLeftTwoBridge;
  741.             move[3] = downRight;
  742.             move[4] = downLeft;
  743.             move[5] = right;
  744.             move[6] = left;
  745.             move[7] = upRight;
  746.             move[8] = upLeft;
  747.             move[9] = upRightTwoBridge;
  748.             move[10] = upLeftTwoBridge;
  749.             move[11] = upTwoBridge;
  750.             break;
  751.         default:
  752.             break; // should never arrive here
  753.     } // end switch
  754. } // end PrioritizeMoves
  755.  
  756. Boolean PossibleMove(long boardSize, Chip *theBoard,
  757.     long row, long col, Path *path, Direction move,
  758.     Chip color)
  759. {
  760.     long newRow, newCol; // where the move leads
  761.     
  762.     // determine where a move in the new direction would
  763.     // lead
  764.     FindNewLocation(row, col, move, &newRow, &newCol);
  765.     // the new location must be on the board and either
  766.     // empty or occupied by a friendly piece; it must also
  767.     // not be in the path already
  768.     if (!OnBoard(boardSize, newRow, newCol)
  769.         || (theBoard[newRow * boardSize + newCol] ==
  770.         (color == blue ? red : blue)) ||
  771.         MoveInPath(path, newRow, newCol))
  772.         return false;
  773.     // if the move forms a two-bridge, there must
  774.     // be no pieces in between the two
  775.     if (IsTwoBridge(move))
  776.     {
  777.         return TwoBridgeFree(boardSize, theBoard, row, col,
  778.             move);
  779.     } // end if
  780.     else
  781.         return true;
  782. } // end PossibleMove
  783.  
  784. void FindNewLocation(long row, long col, Direction move,
  785.     long *newRow, long *newCol)
  786. {
  787.     // handle the row first
  788.     switch (move)
  789.     {
  790.         case upTwoBridge:
  791.             *newRow = row - 2;
  792.             break;
  793.         case upRightTwoBridge:
  794.         case upRight:
  795.         case upLeft:
  796.         case upLeftTwoBridge:
  797.             *newRow = row - 1;
  798.             break;
  799.         case left:
  800.         case right:
  801.             *newRow = row;
  802.             break;
  803.         case downLeftTwoBridge:
  804.         case downLeft:
  805.         case downRight:
  806.         case downRightTwoBridge:
  807.             *newRow = row + 1;
  808.             break;
  809.         case downTwoBridge:
  810.             *newRow = row + 2;
  811.             break;
  812.         default: // should never get here
  813.             break;
  814.     } // end switch
  815.     // then handle the column
  816.     switch (move)
  817.     {
  818.         case downLeftTwoBridge:
  819.             *newCol = col - 2;
  820.             break;
  821.         case upLeftTwoBridge:
  822.         case left:
  823.         case downLeft:
  824.         case downTwoBridge:
  825.             *newCol = col - 1;
  826.             break;
  827.         case upLeft:
  828.         case downRight:
  829.             *newCol = col;
  830.             break;
  831.         case upTwoBridge:
  832.         case upRight:
  833.         case right:
  834.         case downRightTwoBridge:
  835.             *newCol = col + 1;
  836.             break;
  837.         case upRightTwoBridge:
  838.             *newCol = col + 2;
  839.             break;
  840.         default: // should never get here
  841.             break;
  842.     } // end switch
  843. } // end FindNewLocation
  844.  
  845. Direction OppositeDirection(Direction move)
  846. {
  847.     switch (move)
  848.     {
  849.         case upTwoBridge:
  850.             return downTwoBridge;
  851.         case upRightTwoBridge:
  852.             return downLeftTwoBridge;
  853.         case upRight:
  854.             return downLeft;
  855.         case upLeft:
  856.             return downRight;
  857.         case upLeftTwoBridge:
  858.             return downRightTwoBridge;
  859.         case left:
  860.             return right;
  861.         case right:
  862.             return left;
  863.         case downLeftTwoBridge:
  864.             return upRightTwoBridge;
  865.         case downLeft:
  866.             return upRight;
  867.         case downRight:
  868.             return upLeft;
  869.         case downRightTwoBridge:
  870.             return upLeftTwoBridge;
  871.         case downTwoBridge:
  872.             return upTwoBridge;
  873.         default: // should never get here
  874.             break;
  875.     } // end switch
  876. } // end OppositeDirection
  877.  
  878. Boolean OnBoard(long boardSize, long row, long col)
  879. {
  880.     return row >= 0 && row < boardSize && col >= 0 &&
  881.         col < boardSize;
  882. } // end OnBoard
  883.  
  884. Boolean IsTwoBridge(Direction move)
  885. {
  886.     switch (move)
  887.     {
  888.         case upTwoBridge:
  889.         case upRightTwoBridge:
  890.         case upLeftTwoBridge:
  891.         case downLeftTwoBridge:
  892.         case downRightTwoBridge:
  893.         case downTwoBridge:
  894.             return true;
  895.         default:
  896.             return false;
  897.     } // end switch
  898. } // end IsTwoBridge
  899.  
  900. Boolean TwoBridgeFree(long boardSize, Chip *theBoard,
  901.     long row, long col, Direction move)
  902. {
  903.     switch (move)
  904.     {
  905.         case upTwoBridge:
  906.             return theBoard[(row - 1) * boardSize + col] ==
  907.                 empty && theBoard[(row - 1) * boardSize +
  908.                 col + 1] == empty;
  909.         case upRightTwoBridge:
  910.             return theBoard[(row - 1) * boardSize +
  911.                 col + 1] == empty && theBoard[row *
  912.                 boardSize + col + 1] == empty;
  913.         case upLeftTwoBridge:
  914.             return theBoard[(row - 1) * boardSize +
  915.                 col] == empty && theBoard[row *
  916.                 boardSize + col - 1] == empty;
  917.         case downLeftTwoBridge:
  918.             return theBoard[(row + 1) * boardSize +
  919.                 col - 1] == empty && theBoard[row *
  920.                 boardSize + col - 1] == empty;
  921.         case downRightTwoBridge:
  922.             return theBoard[(row + 1) * boardSize +
  923.                 col] == empty && theBoard[row *
  924.                 boardSize + col + 1] == empty;
  925.         case downTwoBridge:
  926.             return theBoard[(row + 1) * boardSize +
  927.                 col] == empty && theBoard[(row + 1) *
  928.                 boardSize + col - 1] == empty;
  929.         default:
  930.             return false;
  931.     } // end switch
  932. } // TwoBridgeFree
  933.  
  934. Boolean PieceOnEdge(long row, long col, long boardSize,
  935.     Edge edge)
  936. {
  937.     switch (edge)
  938.     {
  939.         case leftEdge:
  940.             return col == 0;
  941.         case rightEdge:
  942.             return col == boardSize - 1;
  943.         case topEdge:
  944.             return row == 0;
  945.         case bottomEdge:
  946.             return row == boardSize - 1;
  947.         default: // should never get here
  948.             break;
  949.     } // end switch
  950. } // end PieceOnEdge
  951.  
  952. void FreePath(Path *path)
  953. {
  954.     if (!path)
  955.         return;
  956.     // go to the beginning of the path
  957.     for (; path->prev; path = path->prev);
  958.     // free each node until none are left
  959.     for (; path; path = path->next)
  960.         FreeBlock(path);
  961. } // end
  962.  
  963. Boolean ValidMove(long boardSize, Chip *theBoard,
  964.     long row, long col)
  965. {
  966.     return OnBoard(boardSize, row, col) &&
  967.         theBoard[row * boardSize + col] == empty; // free
  968. } // end ValidMove
  969.  
  970. Disruption MoveInPath(Path *path, long row, long col)
  971. {
  972.     if (!path)
  973.         return noDisruption;
  974.     
  975.     // go to the beginning of the path
  976.     for (; path->prev; path = path->prev);
  977.     // search the path until the end is reached or a node
  978.     // is found matching the desired move
  979.     for (; path; path = path->next)
  980.         // check for a threatened two-bridge
  981.         if (IsTwoBridge(path->nextDirection) &&
  982.             TwoBridgeThreatened(path->row, path->col,
  983.             row, col, path->nextDirection))
  984.         {
  985.             if (path->occupied && path->next->occupied)
  986.                 return inTwoBridge;
  987.             else
  988.                 return inSpot;
  989.         } // end if
  990.         else if (row == path->row && col == path->col)
  991.             return inSpot;
  992.     // if we get here, there are no disruptions
  993.     return noDisruption;
  994. } // end MoveInPath
  995.  
  996. Boolean TwoBridgeThreatened(long row, long col,
  997.     long threatRow, long threatCol, Direction move)
  998. {
  999.     switch (move)
  1000.     {
  1001.         case upTwoBridge:
  1002.             return (threatRow == row - 1) &&
  1003.                 (threatCol == col || threatCol == col + 1);
  1004.         case upRightTwoBridge:
  1005.             return (threatCol == col + 1) &&
  1006.                 (threatRow == row - 1 || threatRow == row);
  1007.         case upLeftTwoBridge:
  1008.             return (threatRow + threatCol == row + col - 1)
  1009.                 && (threatRow == row || threatCol == col);
  1010.         case downLeftTwoBridge:
  1011.             return (threatCol == col - 1) &&
  1012.                 (threatRow == row || threatRow == row + 1);
  1013.         case downRightTwoBridge:
  1014.             return (threatRow + threatCol == row + col + 1)
  1015.                 && (threatRow == row || threatCol == col);
  1016.         case downTwoBridge:
  1017.             return (threatRow == row + 1) &&
  1018.                 (threatCol == col || threatCol == col - 1);
  1019.         default: // should not get here
  1020.             return false;
  1021.     } // end switch
  1022. } // end TwoBridgeThreatened
  1023.  
  1024. void UpdatePath(Path *path, long row, long col)
  1025. {
  1026.     // go to the beginning of the path
  1027.     for (; path->prev; path = path->prev);
  1028.     // search the path until the end is reached or a node
  1029.     // is found matching the desired move
  1030.     for (; path; path = path->next)
  1031.         // check for completion of a two-bridge
  1032.         if (IsTwoBridge(path->nextDirection) &&
  1033.             TwoBridgeThreatened(path->row, path->col,
  1034.             row, col, path->nextDirection))
  1035.         {
  1036.             // destroy the two-bridge and create two new
  1037.             // connections
  1038.             Path *newNode = AllocateBlock(sizeof (Path));
  1039.             
  1040.             newNode->row = row;
  1041.             newNode->col = col;
  1042.             newNode->occupied = true;
  1043.             newNode->center = false;
  1044.             newNode->prevDirection = GetDirection(
  1045.                 row, col, path->row, path->col);
  1046.             newNode->nextDirection = GetDirection(
  1047.                 row, col, path->next->row, path->next->col);
  1048.             newNode->prev = path;
  1049.             newNode->next = path->next;
  1050.             path->nextDirection = OppositeDirection(
  1051.                 newNode->prevDirection);
  1052.             path->next = newNode;
  1053.             newNode->next->prevDirection =
  1054.                 OppositeDirection(newNode->nextDirection);
  1055.             newNode->next->prev = newNode;
  1056.             
  1057.         } // end if
  1058.         else if (row == path->row && col == path->col)
  1059.             path->occupied = true;
  1060. } // end UpdatePath
  1061.  
  1062. Direction GetDirection(long row1, long col1, long row2,
  1063.     long col2)
  1064. {
  1065.     // check for unique cases first
  1066.     if (row2 == row1 + 2)
  1067.         return downTwoBridge;
  1068.     else if (row2 == row1 - 2)
  1069.         return upTwoBridge;
  1070.     else if (col2 == col1 + 2)
  1071.         return upRightTwoBridge;
  1072.     else if (col2 == col1 - 2)
  1073.         return downLeftTwoBridge;
  1074.     // then try the more common ones
  1075.     else if (row2 == row1 - 1)
  1076.         if (col2 == col1 - 1)
  1077.             return upLeftTwoBridge;
  1078.         else if (col2 == col1)
  1079.             return upLeft;
  1080.         else // col2 == col1
  1081.             return upRight;
  1082.     else if (row2 == row1 + 1)
  1083.         if (col2 == col1 - 1)
  1084.             return downLeft;
  1085.         else if (col2 == col1 + 1)
  1086.             return downRightTwoBridge;
  1087.         else // col2 == col1
  1088.             return downRight;
  1089.     else // row2 == row1
  1090.         if (col2 == col1 - 1)
  1091.             return left;
  1092.         else // col2 == col1 + 1
  1093.             return right;        
  1094. } // end GetDirection
  1095.  
  1096. Path *BetterPath(Path *path1, Path *path2,
  1097.     PathAction action)
  1098. {
  1099.     long rating1, rating2;
  1100.     Path *betterPath, *worsePath;
  1101.     
  1102.     // rate both paths
  1103.     rating1 = PathRating(path1);
  1104.     rating2 = PathRating(path2);
  1105.     // compare the ratings (low is better)
  1106.     if (rating1 < rating2)
  1107.     {
  1108.         betterPath = path1;
  1109.         worsePath = path2;
  1110.     } // end if
  1111.     else
  1112.     {
  1113.         betterPath = path2;
  1114.         worsePath = path1;
  1115.     } // end else
  1116.     // dispose of the bad path, if directed to do so
  1117.     if (action == forgetBad)
  1118.         FreePath(worsePath);
  1119.     return betterPath;
  1120. } // end BetterPath
  1121.  
  1122. long PathRating(Path *path)
  1123. {
  1124.     long rating;
  1125.     
  1126.     if (!path)
  1127.         return 4096;
  1128.     // go to the beginning of the path
  1129.     for (; path->prev; path = path->prev);
  1130.     // count the number of unoccupied locations
  1131.     for (rating = 0; path; path = path->next) 
  1132.         if (path->occupied == false)
  1133.             rating++;
  1134.     return rating;
  1135. } // end PathRating
  1136.  
  1137. void FillThreatenedTwoBridge(Path *path, long threatRow,
  1138.     long threatCol, long *row, long *col)
  1139. {
  1140.     // go to the beginning of the path
  1141.     for (; path->prev; path = path->prev);
  1142.     // scan through the path until the threat is found
  1143.     for (; path; path = path->next)
  1144.         if (IsTwoBridge(path->nextDirection) &&
  1145.             TwoBridgeThreatened(path->row, path->col,
  1146.             threatRow, threatCol, path->nextDirection))
  1147.         {
  1148.             // try all moves until we find one that fills
  1149.             // the two-bridge (sorry, it's the easiest way
  1150.             // way to do it)
  1151.             Direction d;
  1152.             Boolean done;
  1153.             
  1154.             for (done = false, d = 0; !done &&
  1155.                 d < noDirection; d++)
  1156.             {
  1157.                 FindNewLocation(path->row, path->col,
  1158.                     d, row, col);
  1159.                 // make sure we're not making the same move
  1160.                 // as the opponent
  1161.                 if (TwoBridgeThreatened(path->row,
  1162.                     path->col, *row, *col,
  1163.                     path->nextDirection) &&    (*row !=
  1164.                     threatRow || *col != threatCol))
  1165.                 {
  1166.                     done = true;
  1167.                 } // end if
  1168.             } // end for
  1169.         } // end if
  1170. } // end FillThreatenedTwoBridge
  1171.  
  1172. Path *TakeDetour(long boardSize, Chip *theBoard, Path *path,
  1173.     long row, long col, Chip color)
  1174. {
  1175.     Boolean centerPassed; // have we passed the center?
  1176.     Boolean blockFound; // have we located the disruption?
  1177.     Path *corruptPath; // the part that was blocked
  1178.     Edge edge;
  1179.     
  1180.     // go to the beginning of the path
  1181.     for (; path->prev; path = path->prev);
  1182.     // find the location of the disruption
  1183.     for (centerPassed = blockFound = false; path &&
  1184.         !blockFound;)
  1185.     {
  1186.         if (path->center)
  1187.             centerPassed = true;
  1188.         
  1189.         if (IsTwoBridge(path->nextDirection) &&
  1190.             TwoBridgeThreatened(path->row, path->col,
  1191.             row, col, path->nextDirection))
  1192.         {
  1193.             if (centerPassed)
  1194.                 path = path->next;
  1195.             blockFound = true;
  1196.         } // end if
  1197.         else if (row == path->row && col == path->col)
  1198.             blockFound = true;
  1199.         else
  1200.             path = path->next;
  1201.     } // end for
  1202.     // free from there to the end
  1203.     if (centerPassed)
  1204.     {
  1205.         corruptPath = path;
  1206.         path = path->prev;
  1207.         path->next = corruptPath->prev = nil;
  1208.         FreePath(corruptPath);
  1209.     } // end if
  1210.     else
  1211.     {
  1212.         corruptPath = path;
  1213.         path = path->next;
  1214.         corruptPath->next = path->prev = nil;
  1215.         FreePath(corruptPath);
  1216.     } // end else
  1217.     if (color == blue)
  1218.         if (centerPassed)
  1219.             edge = bottomEdge;
  1220.         else
  1221.             edge = topEdge;
  1222.     else // color is red
  1223.         if (centerPassed)
  1224.             edge = rightEdge;
  1225.         else
  1226.             edge = leftEdge;
  1227.     // extend the path from there to the edge
  1228.     if (!ExtendPathToEdge(boardSize, theBoard, path, edge))
  1229.     {
  1230.         // if not possible, destroy the path
  1231.         FreePath(path);
  1232.         path = nil;
  1233.     } // end if
  1234.     
  1235.     return path;
  1236. } // end TakeDetour
  1237.  
  1238. void FindBestMove(Path *ourPath, Path *oppPath, long *row,
  1239.     long *col)
  1240. {
  1241.     // ratings for our path, the opponent's path, and the
  1242.     // two halves of the better (used) path
  1243.     long ourRating, oppRating, prevRating = 0,
  1244.         nextRating = 0;
  1245.     Path *usedPath, *tempPath, *unusedPath;
  1246.     
  1247.     // don't even try to continue if there are no paths
  1248.     if (!oppPath && !ourPath)
  1249.         return;
  1250.     // see who has the better path
  1251.     ourRating = PathRating(ourPath);
  1252.     oppRating = PathRating(oppPath);
  1253.     if (ourRating < oppRating) // ours is better
  1254.     {
  1255.         usedPath = ourPath;
  1256.         unusedPath = oppPath;
  1257.     }
  1258.     else
  1259.     {
  1260.         usedPath = oppPath;
  1261.         unusedPath = ourPath;
  1262.     }
  1263.     // first try to make a move which is both offensive
  1264.     // and defensive
  1265.     tempPath = usedPath;
  1266.     // go to the beginning
  1267.     for (; tempPath->prev; tempPath = tempPath->prev);
  1268.     // find the first unoccupied piece
  1269.     for (; tempPath && tempPath->occupied;
  1270.         tempPath = tempPath->prev)
  1271.     {
  1272.         // see if it is in the other path, also
  1273.         if (MoveInPath(unusedPath, tempPath->row,
  1274.             tempPath->col))
  1275.         {
  1276.             *row = tempPath->row;
  1277.             *col = tempPath->col;
  1278.             return;
  1279.         }
  1280.     }
  1281.     // look for unoccupied pieces
  1282.     tempPath = usedPath;
  1283.     // go to the beginning
  1284.     for (; tempPath->prev; tempPath = tempPath->prev);
  1285.     // go to the center
  1286.     for (; !tempPath->center; tempPath = tempPath->next);
  1287.     // rate the first half
  1288.     for (; tempPath; tempPath = tempPath->prev)
  1289.         prevRating += !tempPath->occupied;
  1290.     tempPath = usedPath;
  1291.     // go to the beginning
  1292.     for (; tempPath->prev; tempPath = tempPath->prev);
  1293.     // go back to the center
  1294.     for (; !tempPath->center; tempPath = tempPath->next);
  1295.     // rate the second half
  1296.     for (; tempPath; tempPath = tempPath->next)
  1297.         nextRating += !tempPath->occupied;
  1298.     tempPath = usedPath;
  1299.     // go to the beginning
  1300.     for (; tempPath->prev; tempPath = tempPath->prev);
  1301.     // go to the center
  1302.     for (; !tempPath->center; tempPath = tempPath->next);
  1303.     // make a move on the side with the worse (high) rating
  1304.     if (prevRating > nextRating)
  1305.         // find the first unoccupied piece
  1306.         for (; tempPath && tempPath->occupied;
  1307.             tempPath = tempPath->prev);
  1308.     else
  1309.         // find the first unoccupied piece
  1310.         for (; tempPath && tempPath->occupied;
  1311.             tempPath = tempPath->next);
  1312.     if (tempPath)
  1313.     {
  1314.         *row = tempPath->row;
  1315.         *col = tempPath->col;
  1316.     } // end if
  1317.     else // no unoccupied pieces anywhere
  1318.     {
  1319.         // if there are none, fill in any unconnected
  1320.         // two-bridges
  1321.         for (; usedPath->prev; usedPath =
  1322.             usedPath->prev);
  1323.         for (; usedPath && !IsTwoBridge(
  1324.             usedPath->nextDirection);
  1325.             usedPath = usedPath->next);
  1326.         if (usedPath) // should always be true
  1327.         {
  1328.             // try all moves until we find one that
  1329.             // fills the two-bridge (sorry, it's the
  1330.             // easiest way way to do it)
  1331.             Direction d;
  1332.             Boolean done;
  1333.             
  1334.             for (done = false, d = 0; !done &&
  1335.                 d < noDirection; d++)
  1336.             {
  1337.                 FindNewLocation(usedPath->row,
  1338.                     usedPath->col, d, row, col);
  1339.                 if (TwoBridgeThreatened(usedPath->row,
  1340.                     usedPath->col, *row, *col,
  1341.                     usedPath->nextDirection))
  1342.                 {
  1343.                     done = true;
  1344.                 } // end if
  1345.             } // end for
  1346.         } // end if
  1347.     } // end else
  1348. } // end FindBestMove
  1349.  
  1350. Boolean NextToEdge(long row, long col, long boardSize,
  1351.     Edge edge)
  1352. {
  1353.     switch (edge)
  1354.     {
  1355.         case leftEdge:
  1356.             return col == 1;
  1357.         case rightEdge:
  1358.             return col == boardSize - 2;
  1359.         case topEdge:
  1360.             return row == 1;
  1361.         case bottomEdge:
  1362.             return row == boardSize - 2;
  1363.         default: // should never get here
  1364.             break;
  1365.     } // end switch
  1366. } // end NextToEdge
  1367.